The present invention generally relates to the caching of web objects on network proxy servers located between client machines and content servers.
In recent years, the growth of the Internet has exploded, especially with regard to the World Wide Web. As a consequence, user response times for accessing the Web have become increasingly unsatisfactory.
One common conventional approach to improving Web performance is to deploy proxy cache servers between clients and content servers. With proxy caching, most client requests can be serviced by the proxy caches, reducing latency delays. Network traffic on the Internet can also be significantly reduced in this manner, thus greatly reducing network congestion. In fact, many commercial companies are providing hardware and software products and solutions for Web caching, such as IBM, Sun Microsystems, Inktomi, Network Appliance and Akamai. Some of them are using geographically distributed data centers for collaborative web caching. Namely, many geographically distributed proxies are increasingly used to collaborate in web caching.
To collaborate in web caching, a coordinating protocol is generally required. Hash routing is an emerging approach to coordinating a collection of collaborating proxy caches. Examples of hash routing include the xe2x80x9ccache array routing protocolxe2x80x9d (CARP) and xe2x80x9cconsistent hashingxe2x80x9d. In xe2x80x9cCache Array Routing Protocol, v 1.0,xe2x80x9d (Internet Draft, http://www.ircache.net/Cache/ICP/carp.txt, February 1998, V. Valloppillil and K. W. Ross), the draft of CARP is described. In xe2x80x9cHash-Routing for Collections of Shared Web Caches,xe2x80x9d (IEEE Network Magazine, pp. 37-44, November-December 1997, K. W. Ross), the performance of CARP and other protocols is analyzed. In xe2x80x9cWeb Caching with Consistent Hashing,xe2x80x9d (Proc. Of 8th International World Wide Web Conference, pp. 125-135, 1999, D. Karger et al.), the application of consistent hashing to web caching is described
Basically, hashing partitions the entire URL space among the caches, creating a single logical cache. Each cache is responsible for requests belonging to the assigned partition. Requests are sent to the proper proxy caches based on the hash values of the corresponding URLs. The mapping between hash values and proxy cache IDs can be done either by the browsers or by the domain name servers (DNS).
More and more geographically distributed proxies are used in collaborative web caching. For example, commercial companies, such as Akamai and Inktomi, are using cache servers residing on geographically distributed data centers for web caching. As a result, response times tend to be negatively impacted for those requests hashed into geographically distant proxies or overloaded proxies. Distant proxies tend to incur longer network latency delays. Overloaded proxies can cause significant delays as well, no matter how close they are to the browsers. As a result, a user may experience unpredictably slow response times for certain URL requests that are hashed into far away or overloaded proxy caches.
However, traditional hashing-based approach to collaborative web caching does not deal with network latency. It either avoids hashing into geographically distant proxy caches or hashes to all proxy caches regardless of network latency. For example, in xe2x80x9cWeb Caching with Consistent Hashing,xe2x80x9d (Proc. Of 8th International World Wide Web Conference, pp. 125-135, 1999), a user""s geographical region is encoded into the hash value and sent by the browser to a DNS in its geographical region. The DNS then maps the encoded hash value to a proxy cache ID within the same region. Thus, requests are served only by proxies in a geographically close region. It works well if the proxy caches within a region can adequately service all the requests originated within the same region. However, if workloads are skewed among regions, proxies in one region may be overloaded while those in another region are underloaded. As a result, the degree of collaboration among proxies is limited by geographical locations.
On the other hand, one can simply hash requests into all collaborating proxy caches regardless of geographical locations. In this case, load tends to be more balanced among all the geographically distributed cooperating caches. However, it does not take into account network latency delays due to geographical distances. It does not deal with xe2x80x9chot spotsxe2x80x9d, either. A xe2x80x9chot spotxe2x80x9d may be defined as a website or web page that experiences tremendous demand over a very short period of time, or a brief xe2x80x9cspikexe2x80x9d in the number of users wishing to access the website or web page. In the presence of hot spots, all the references to the hot spots are hashed into the same proxies. As a result, the proxies that handle the hot spots can easily become overloaded.
Therefore, a need has been recognized in connection with attending to the latency issue in hashing-based web caching. More specifically, a need has been recognized in connection with providing a latency-sensitive hashing for collaborative web caching among geographically distributed proxy caches.
In accordance with the at least one presently preferred embodiment of the present invention, the mentioned latency problems associated with the hashing-based approach to collaborative web caching are solved. Latency-sensitive hashing systems and methods are contemplated herein for collaborative web caching among geographically distributed proxy caches.
In one embodiment of the present invention, URL requests are hashed into all proxies. However, it takes into account latency delays and potential overloaded proxies in choosing the target proxy for a request. In one embodiment of the present invention, a request is first hashed into an anchor hash partition. Each hash partition is mapped to one of the geographically distributed proxies. Secondly, a selection algorithm is used to pick a proxy among a small number of hash partitions adjacent to the anchor hash partition. The selection is based on an objective to reduce network latency and to avoid creating overloaded proxies.
For a better understanding of the present invention, together with other and further features and advantages thereof, reference is made to the following description, taken in conjunction with the accompanying drawings, and the scope of the invention will be pointed out in the appended claims.